/*================================================================
*   Copyright (C) 2024 baichao All rights reserved.
*
*   文件名称：main.c
*   创 建 者：baichao
*   创建日期：2024年06月15日
*   描    述：
*
================================================================*/

#include <stdio.h>
#include <stdlib.h>

// 定义二叉树节点的结构体
struct TreeNode {
  int val;
  struct TreeNode* left;
  struct TreeNode* right;
};

int* inorderTraversal(struct TreeNode* root, int* returnSize) {
  *returnSize = 0;

  // 判断 root 是否为空
  if (root == NULL) {
    return NULL;
  }

  // 结果数组，题目显示最多有 100 个节点，可以根据实际情况调整
  int* result = (int*)malloc(100 * sizeof(int));

  // 栈，用于存储节点
  struct TreeNode** stack =
      (struct TreeNode**)malloc(100 * sizeof(struct TreeNode*));
  memset(stack, 0, 100 * sizeof(struct TreeNode*));
  int stackSize = 0;

  // 当前节点，从根节点开始
  struct TreeNode* currentNode = root;

  // 遍历树
  while (currentNode != NULL || stackSize > 0) {
    while (currentNode != NULL) {
      stack[stackSize++] = currentNode;
      currentNode = currentNode->left;
    }

    currentNode = stack[--stackSize];
    result[(*returnSize)++] = currentNode->val;

    currentNode = currentNode->right;
  }

  // 释放栈的内存
  free(stack);

  // 返回结果数组
  return result;
}

// 辅助函数，用于创建一个新的树节点
struct TreeNode* createNode(int val) {
  struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
  newNode->val = val;
  newNode->left = NULL;
  newNode->right = NULL;
  return newNode;
}

// 辅助函数，用于简单地打印二叉树（以中序方式显示）
void printTree(struct TreeNode* root) {
  if (root == NULL) return;
  printTree(root->left);
  printf("%d ", root->val);
  printTree(root->right);
}

// 辅助函数，用于释放二叉树的所有节点
void freeTree(struct TreeNode* root) {
  if (root == NULL) return;
  freeTree(root->left);
  freeTree(root->right);
  free(root);
}

int main() {
  //            1
  //          /   \
  //         2     3
  //        / \   / \
  //       4   5 6   7
  //      / \
  //     8   9
  struct TreeNode* root = createNode(1);
  root->left = createNode(2);
  root->right = createNode(3);
  root->left->left = createNode(4);
  root->left->right = createNode(5);
  root->right->left = createNode(6);
  root->right->right = createNode(7);
  root->left->left->left = createNode(8);
  root->left->left->right = createNode(9);

  // 打印二叉树结构（以中序方式）
  printf("二叉树结构（中序遍历）：");
  printTree(root);
  printf("\n");

  // 存储遍历结果的大小
  int returnSize;

  // 调用 inorderTraversal 函数
  int* result = inorderTraversal(root, &returnSize);

  // 打印中序遍历结果
  printf("中序遍历结果：");
  for (int i = 0; i < returnSize; i++) {
    printf("%d ", result[i]);
  }
  printf("\n");

  // 释放遍历结果数组的分配内存
  free(result);

  // 释放二叉树节点的分配内存
  freeTree(root);

  return 0;
}
